\section{Introduction}
In the bomber-battleship game, a ship travels along a graph and a bomber tries to bomb the ship. 
The problem is that the bomb does not explode immediately when it is dropped, this takes some time in which the ship can still move. 

The original problem is played on a $n$-restricted graph and the ship has to move every step; it cannot stay at the current place. 
The bomb needs two time units to explode (two-move lag).  A $n$-restricted graph for the two-move lag is a graph were there are $n+1$ outgoing edges from every vertex and there are no cycles of length four. 
Because of the two-move lag it only makes sense for the bomber to drop the bomb on the ship's current place or two steps away (front or back) from it. 
In the example of figure \ref{GraphN2}, where the ship is currently at node 0, it can be concluded that the ship is after two 
time steps at either node \textit{-2, 0} or \textit{2}. 
Hence the bomber should only bomb one of these nodes. \cite{Ferguson}

\begin{figure}[h]
\begin{center}
 \includegraphics[width=3in]{Bilder/2restrictedGraph}
\caption{Part of an one-restricted graph}
\label{GraphN2}
\end{center}
\end{figure}

In this report the focus lies on the original problem and the following extensions of this problem:
\begin{itemize}

\item The ship can stay still.
\item The bomb needs three time units to explode (three-move lag).
\item The construction of a simple discrete time, continuous state model for the problem, where the ship can move in the plane with a certain speed and the bomber 
can bomb any point of the plane and hits anything within a radius.
\end{itemize}

The bomber's aim is hitting the ship. The ship wants to survive. 
Therefore the best strategy for each of them has to be found, which gives them a certain probability to win. 
Ferguson shows that for the two-move lag the ship can ensure that the probability to be hit is less than $v_n$, while the bomber can ensure to hit the ship with a probability greater or 
equal than $\omega$. \cite{Ferguson} 
For the first extension where the ship can stay still, the ship should change its strategy, because than the hit probability can be reduced. 
For the second extension with the three-move lag, the ($\epsilon$-)optimal strategies for the two-move lag are, unfortunely, not optimal for the three-move lag. 

In the beginning, in section \ref{Strategy2Lag} the focus lies on the original problem and the optimal strategies for the ship and the bomber. 
The modification where the bomb needs three time units to explode is handled in section \ref{Strategy3Lag}. There different strategies for the ship specially suited to the three-move lag are presented. Moreover, it is shown why the two-move lag bomber strategy cannot be applied and a bomber which observes the ship's movement is introduced. 
Section \ref{ShipCanStandStill} shows how the ship has to change its strategy if it has the possibility to stay still. In section \ref{continuousStateModel} the continuous state model is established. This section also shows the transformation of the 
continuous state model into a hidden Markov model. The test results can be found in section \ref{Tests}. The different strategies for ship and bomber are playing against each other and by counting the number of hits the value 
of the game can be determined. In the end, section \ref{Conclusion} gives the conclusion and some suggestions for possible future work are given.
